#!/usr/bin/python3

class Vertex:
    def __init__(self, name):
        self.name = name
    
    def __repr__(self):
        return self.name 

class Edge:
    def __init__(self, s, t, capacity, flow=0):
        self.s = s
        self.t = t
        self.capacity = capacity
        self.flow = flow
        
        self.origin = self
        
        self.backward = False
        
        self.residual_forward_edge = None
        self.residual_backward_edge = None
    
    def is_residual(self):
        return not self.origin == self
    
    def get_residual_edges(self):
        if self.is_residual():
            return None
        
        if not self.residual_backward_edge:
            self.residual_backward_edge = Edge(self.s, self.t, self.flow)
            self.residual_backward_edge.origin = self
            self.residual_backward_edge.backward = True
            
        if not self.residual_forward_edge:
            if self.is_unlimited():
                self.residual_forward_edge = Edge(self.t, self.s, -1)
            else:
                self.residual_forward_edge = Edge(self.t, self.s, self.capacity - self.flow)
            self.residual_forward_edge.origin = self
        
        return (self.residual_backward_edge, self.residual_forward_edge)
    
    def is_unlimited(self):
        return self.capacity == -1
    
    def residual_capacity(self):
        if not self.is_unlimited():
            assert 0 <= self.capacity - self.flow
            return self.capacity - self.flow
        return self.capacity           
            
    def has_capacity(self):
        return self.capacity == -1 or self.flow < self.capacity
    
    def update(self):
        self.residual_backward_edge.capacity = self.flow
        if not self.is_unlimited():
            self.residual_forward_edge.capacity = self.capacity - self.flow 
                    
    def increase_flow(self, flow):
        self.flow += flow
        self.update()
    
    def decrease_flow(self, flow):
        self.flow -= flow
        self.update()
    
    def __repr__(self):
        if self.backward:
            return " %s <- %s: %d (%d)" %(self.t, self.s, self.flow, self.capacity)
        return "%s -> %s: %d (%d)" %(self.s, self.t, self.flow, self.capacity)
    
class Path:
    def __init__(self):
        self.edges = []
        
    def bottleneck(self):
        return min([edge.capacity for edge in self.edges if not edge.is_unlimited()])
        
    def augment(self):
        b = self.bottleneck()
        for edge in self.edges:
            if edge.backward:
                edge.origin.decrease_flow(b)
            else:
                edge.origin.increase_flow(b)

class Graph:
    def __init__(self, V, E):
        self.V = V
        self.E = E
        self.residual_graph = None
    
    def residual(self):
        if not self.residual_graph:
            rE = list()
            for edge in self.E:
                residuals = edge.get_residual_edges()
                rE.append(residuals[0])
                rE.append(residuals[1])
            self.residual_graph = Graph(self.V, rE)
        return self.residual_graph
    
    def edges(self, v):
        return [edge for edge in self.E if edge.s == v or edge.t == v]
    
    def internal_find_path(self, s, t, path, visited):
        if s not in visited:
            if s == t:
                return path
            
            visited.append(s)
            for edge in self.edges(s):
                if edge.has_capacity():
                    path.edges.append(edge)
                    p = self.internal_find_path(edge.t, t, path, visited)
                    if p:
                        return p
                    path.edges.remove(edge)
        return None
    
    def find_path(self, s, t):        
        return self.internal_find_path(s, t, Path(), [])
            
    def find_max_flow(self, s, t):
        rgraph = self.residual()
        p = rgraph.find_path(s, t)
        while p:
            p.augment()
            p = rgraph.find_path(s, t)
        return self.current_flow(s)
    
    def find_min_cut(self, s, t):
        max_flow = self.find_max_flow(s, t)
        A = []
        self.residual().internal_find_path(s, t, Path(), A)
        B = [v for v in self.V if v not in A]
        min_cut = [edge for edge in self.E if edge.s in B and edge.t in A]
        return max_flow, min_cut
                        
    def current_flow(self, v):
        return sum([edge.flow for edge in self.edges(v)])
    
def parse(arg):
    vertices = []
    edges = []
    t = None
    s = None 
    
    mode = ""
    with open(arg, "r") as file:
        for line in file:
            string = line.rstrip()
            if string == "ORIGINS":
                mode = "v"
            if mode == "v":
                vertex = Vertex(string)
                vertices.append(vertex)
                if string == "ORIGINS":
                    s = vertex
                elif string == "DESTINATIONS":
                    t = vertex
                    mode = "e"
                    if arg.endswith("rail.txt"):
                        assert len(vertices) == 55                
            elif mode == "e":
                indices = [int(i) for i in string.split(" ")]
                if len(indices) == 3:
                    # edges are not directed!
                    edge_a = Edge(vertices[indices[0]], vertices[indices[1]], indices[2])
                    edge_b = Edge(vertices[indices[1]], vertices[indices[0]], indices[2])
                    edges.append(edge_a)
                    edges.append(edge_b)
    
    return vertices, edges, s, t

if __name__ == "__main__":
    import sys
    
    for arg in sys.argv[1:]:
        vertices, edges, s, t = parse(arg)
        g = Graph(vertices, edges)
        max_flow, min_cut = g.find_min_cut(s, t)
        print(max_flow)
        for mc in min_cut:
            print(mc)